package algorithm7.leetcode.hot100.c2双指针;

import org.junit.jupiter.api.Test;

/**
 * @author merrick.peng
 */
public class h4_LC283移动零 {
//2
    public void moveZeroes(int[] nums) {
//        handle1(nums);
//        handle2(nums);
//        handle3(nums);
//        handle4(nums);
        handle5(nums);
    }

    private void handle5(int[] nums) {
        int l = 0, r= 0, n = nums.length;
        while (r < n) {
            // 右指针碰到非0，和左指针交换；
            // 如果左指针是非0，此时左右指针必定相等。直接交换即可[等于没有交换]，交换玩左右指针同时右移，开始下一轮
            if (nums[r] != 0) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                l++;
            }
            r++;
        }
    }

    private void handle4(int[] nums) {
        int l = 0, r= 0, n = nums.length;
        while (l < n - 1) {
            // 左指针碰到0，右指针右移找到第一个非0
            boolean f = false;
            if (nums[l] == 0) {
                r = l + 1;
                while (r < n - 1) {
                    if (nums[r] != 0) {
                        f = true;
                        break;
                    }
                    r++;
                }
                // 交换
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                if (!f) {
                    break;
                }
            }
            l++;
        }
    }

    private void handle3(int[] nums) {
        int n = nums.length;
        int l = 0;
        int r = 0;
        // 和题目反着移动，将不为0的下标依次向前交换（l指针每交换一次+1，r指针每次+1）
        while (r < n) {
            if (nums[r] != 0) {
                // 只要又指针不为0，就往前移(和l交换)
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                // 发生交换，l+1
                l++;
            }
            // 每轮r+1
            r++;
        }
    }

    private void handle2(int[] nums) {
        int n = nums.length;
        int l = 0;
        int r = 0;
        while (r < n) {
            if (nums[r] != 0) {
                int temp = nums[l];
                nums[l] = nums[r];
                nums[r] = temp;
                ++l;
            }
            ++r;
        }
    }

    private void handle1(int[] nums) {
        int i = 0;
        int j = 1;
        int n = nums.length;
        while (i < n - 1) {
            if (nums[i] != 0) {
                ++i;
                ++j;
            } else {
                // 第一个为0的位置 nums[i] == 0
                // 找到后面第一个不为0的位置 nums[j] != 0
                while (j <= n - 1 && nums[j] == 0) {
                    ++j;
                }
                if (j > n - 1) {
                    return;
                }
                // nums[i] 和 nums[j] 交换
                int temp = nums[i];
                nums[i] = nums[j];
                nums[j] = temp;
                ++i;
                j = i + 1;
            }
            if (j > n - 1) {
                return;
            }
        }
    }

    /*

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:
输入: nums = [0]
输出: [0]

     */

    @Test
    void t() {
        int[] nums = {0, 1, 0, 3, 12};
//        int[] nums = {1, 2, 3, 4, 5, 6};
        moveZeroes(nums);
        System.out.println();
    }

}
